package P1线性结构.LeetCode单调栈;

import java.util.ArrayDeque;

public class LeetCode402 {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < num.length(); i++) {
            char digit = num.charAt(i);
            while (!stack.isEmpty() && k > 0 && digit < stack.peekLast()) {
                stack.pollLast();
                k--;
            }
            //进栈 栈为空 或 新来的大于等于栈顶 或 新来的小于栈顶但删除次数不够
            stack.offerLast(digit);
        }
        //此时 k 它不一定使用完毕 所以接着删除表尾k个元素
        for (int i = 0; i < k; i++) {
            stack.pollLast();
        }
        //解下来处理前导零
        //从左到右遍历 一直到第一个非0元素截止
        // "001023" => "1023"
        StringBuilder sb = new StringBuilder();
        boolean flag = true;    //假设没有前导零
        while (!stack.isEmpty()) {
            char digit = stack.pollFirst();
            if (flag && digit == '0') {
                continue;
            }
            flag = false;
            sb.append(digit);
        }
        //"10012" k = 2
        // 00
        return sb.length() == 0 ? "0" : sb.toString();
    }
}
